Dynamic provisioning of bandwidth guaranteed paths with fast restoration capability is an important network service feature for the emerging Multi-Protocol Label Switched (MPLS) networks and optical mesh networks. The fast restoration capabilities are required in order to provide the needed reliability for services such as packetized voice, critical virtual private network (VPN) traffic, etc. Traditionally ring-based synchronous optical networks (SONETs) have offered 50 millisecond (ms) restoration to bandwidth guaranteed services, using pre-reserved spare protection capacity and pre-planned protection paths. Pre-planning protection in rings has been especially attractive, because of the availability of exactly one backup path between any two nodes, leading to very simple and fast automatic protection switching mechanisms. However, in ring-based SONET networks, these advantages come at the cost of reserving at least half the total capacity for protection.
A local restoration scheme has been proposed to provide fast restoration in mesh-based MPLS and optical networks. In this scheme, which is also referred to as link restoration, the traffic on each link e of the network is protected by a detour path that does not include link e. Upon failure of any link e, any traffic on e is switched to its detour path. Thus, link restoration provides a local mechanism to route around a failure. In this restoration scheme, the restoration capacity of the pre-setup detours is not used under normal no-failure conditions (except possibly by low priority preemptible traffic).
The main approaches for supporting a pre-provisioned link restoration scheme in mesh networks are based on identifying ring structures. Once the set of rings is identified, pre-planned restoration schemes (as in SONETs) are employed. In some of these approaches, the network is designed in terms of rings or by partially using rings. Thus, these schemes are only applicable to constrained topologies. In some other of these approaches, each link is covered by a cycle leading to a cycle cover for the network. Each of these cycles is then provisioned with enough protection capacity to cover the links that belong to it. On the failure of the link, the working traffic is rerouted over the protection capacities in the surviving links of the covering cycle. There are two drawbacks to these approaches: first, the amount of pre-provisioned protection capacity can be significant; and, second, it is hard to find the smallest cycle cover of a given network.
An improvement to these schemes is based on the notion of p-cycle. Here, the main idea is that a cycle can be used to protect not just the links on the cycle but also the chords (spokes) of the cycle, thus showing that far fewer cycles (than in a cycle cover) may be sufficient for providing full protection.
An alternative to cycle covers, intended to overcome the difficulty of finding good covers, is to cover every link in a network with exactly two cycles. A set of cycles that meets this requirement is called a double cycle cover. For planar graphs, double cycle covers can be found in polynomial-time. For non-planar graphs, it is conjectured that double cycle covers exist, and they are typically found quickly in practice. However, even for double cycle cover-based protection schemes, the required pre-provisioned protection capacity can be significant.
Non-ring based approaches to link restoration on mesh networks include generalized loop back, where the main idea is to select a digraph, called the primary, such that the conjugate digraph, called the secondary, can be used to carry the switched traffic for any link failure in the primary. Existing approaches have considered the problem of adding protection capacity to the links of a given network (primary) carrying working traffic, at minimum cost, so that the resulting network is capable of supporting link protection for a given set of links, where the protection is provided to the working traffic on the primary network. In such models, no limit is imposed on the total capacities of the links, and they provide a 4-approximation algorithm when all links in the original primary network have uniform bandwidth (carrying the same amount of working traffic) and they provide a 10.87-approximation algorithm for the general case. In addition, a O(log n)-approximation algorithm has been proposed for the problem of jointly designing the primary and protected networks, given a demand matrix for the working traffic.
All the schemes mentioned above assume that protection is provided for a single link failure. A heuristic has been proposed for protecting against two link failures, based on link restoration. While the problem of survivable network design has also been extensively studied, most of the work has focused on obtaining strong relaxations to be used in cutting plane methods.
However, improved network design techniques for supporting fast restoration are needed.